home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / bool_lib / bool-2d.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-14  |  20.1 KB  |  576 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle Boolean operation between two polygons in the XY plane. *
  7. * The Z coords. are totally ignored. Input polygons are assumed to be convex.*
  8. *****************************************************************************/
  9.  
  10. /* #define DEBUG2             If defined, defines some printing routines. */
  11.  
  12. #include <stdio.h>
  13. #include <ctype.h>
  14. #include <math.h>
  15. #include <string.h>
  16. #include <signal.h>
  17. #include "irit_sm.h"
  18. #include "allocate.h"
  19. #include "bool_loc.h"
  20. #include "convex.h"
  21. #include "geomat3d.h"
  22. #include "intrnrml.h"
  23.  
  24. #define Z_CROSS_PROD(V1, V2) (V1[0] * V2[1] - V1[1] * V2[0])
  25.  
  26. typedef struct Bool2DInterStruct {  /* Hold info. on two intersetion points. */
  27.     struct Bool2DInterStruct *Pnext;
  28.     IPVertexStruct *Poly1Vrtx, *Poly2Vrtx;  /* Pointer to Pl1/2 inter. vrtx. */
  29.     RealType Param1, Param2;     /* Parametrization along the poly vertices. */
  30.     PointType InterPt;
  31.     VectorType Normal;
  32. } Bool2DInterStruct;
  33.  
  34. static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
  35.                      IPPolygonStruct *Pl2);
  36. static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
  37.                      IPPolygonStruct *Pl2);
  38. static Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Pl1,
  39.                          IPPolygonStruct *Pl2);
  40. static void SortParam(Bool2DInterStruct **Bool2D, int First);
  41. static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
  42.                             IPPolygonStruct *Pl2,
  43.                             Bool2DInterStruct **Bool2D,
  44.                             int Pl1First, int ComputeOut);
  45. static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead);
  46.  
  47. #ifdef DEBUG2
  48. static void PrintVrtxList(IPVertexStruct *V);
  49. #endif /* DEBUG2 */
  50.  
  51. /*****************************************************************************
  52. * DESCRIPTION:                                                               M
  53. *   Given two polygons assumed to be in the same plane, compute their 2D     M
  54. * Boolean operation BoolOper and return it as a new polygon.             M
  55. * NULL is returned if an error occur (No intersection or invalid BoolOper).  M
  56. *                                                                            *
  57. * PARAMETERS:                                                                M
  58. *   Pl1:        First polygon to compute 2D Boolean for.                     M
  59. *   Pl2:        Second polygon to compute 2D Boolean for.                    M
  60. *   BoolOper:   Boolean operation requested (and, or, etc.)                  M
  61. *                                                                            *
  62. * RETURN VALUE:                                                              M
  63. *   IPPolygonStruct: The resulting Boolean operation.                        M
  64. *                                                                            *
  65. * KEYWORDS:                                                                  M
  66. *   Boolean2D, Booleans                                                      M
  67. *****************************************************************************/
  68. IPPolygonStruct *Boolean2D(IPPolygonStruct *Pl1,
  69.                IPPolygonStruct *Pl2,
  70.                BoolOperType BoolOper)
  71. {
  72.     IPPolygonStruct *RetVal;
  73.     Bool2DInterStruct
  74.     *Bool2D = Boolean2DComputeInters(Pl1, Pl2);
  75.  
  76.     if (Bool2D == NULL) {
  77.     IPPolygonStruct *PlOut, *PlIn;
  78.  
  79.     /* Coplanar polygons have no intersection. Test for inclusion. */
  80.     if ((CGPolygonRayInter(Pl1, Pl2 -> PVertex -> Coord, 0) & 0x01) == 1) {
  81.         /* Pl2 is enclosed within Pl1 */
  82.         PlOut = Pl1;
  83.         PlIn = Pl2;
  84.     }
  85.     else if ((CGPolygonRayInter(Pl2,
  86.                     Pl1 -> PVertex -> Coord, 0) & 0x01) == 1) {
  87.         /* Pl1 is enclosed within Pl2 */
  88.         PlOut = Pl2;
  89.         PlIn = Pl1;
  90.     }
  91.     else {
  92.         PlOut = NULL;
  93.         PlIn = NULL;
  94.     }
  95.  
  96.     RetVal = NULL;
  97.     switch (BoolOper) {
  98.         case BOOL_OPER_OR:
  99.             if (PlOut != NULL)
  100.             RetVal = IPAllocPolygon(PlOut -> Count, PlOut -> Tags,
  101.                   CopyVertexList(PlOut -> PVertex), NULL);
  102.         break;
  103.         case BOOL_OPER_AND:
  104.             if (PlIn != NULL)
  105.             RetVal = IPAllocPolygon(PlIn -> Count, PlIn -> Tags,
  106.                   CopyVertexList(PlIn -> PVertex), NULL);
  107.         break;
  108.         case BOOL_OPER_SUB:
  109.         if (PlOut == Pl1) {
  110.             /* Merge the two polygons PlOut as is and PlIn reversed. */
  111.             RetVal = MergeTwoPolygons(
  112.             IPAllocPolygon(PlOut -> Count, PlOut -> Tags,
  113.                        CopyVertexList(PlOut -> PVertex), NULL),
  114.             IPAllocPolygon(PlIn -> Count, PlIn -> Tags,
  115.                        CopyVertexList(PlIn -> PVertex), NULL));
  116.         }
  117.         break;
  118.         default:
  119.         IritFatalError("Unsupported 2D Boolean operation");
  120.         RetVal = NULL;
  121.         break;
  122.     }
  123.  
  124.     return RetVal;
  125.     }
  126.  
  127.     switch (BoolOper) {
  128.     case BOOL_OPER_OR:
  129.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  130.                                   TRUE, TRUE),
  131.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  132.                                   FALSE, TRUE));
  133.         break;
  134.     case BOOL_OPER_AND:
  135.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  136.                                   TRUE, FALSE),
  137.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  138.                                   FALSE, FALSE));
  139.         break;
  140.     case BOOL_OPER_SUB:
  141.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  142.                                   TRUE, TRUE),
  143.                       Boolean2DReverse(
  144.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  145.                                   FALSE, FALSE)));
  146.         break;
  147.     default:
  148.         IritFatalError("Unsupported 2D Boolean operation");
  149.         RetVal = NULL;
  150.         break;
  151.     }
  152.  
  153.     while (Bool2D) {
  154.     Bool2DInterStruct
  155.         *NextBool2D = Bool2D -> Pnext;
  156.  
  157.     IritFree((VoidPtr) Bool2D);
  158.     Bool2D = NextBool2D;
  159.     }
  160.  
  161.     return RetVal;
  162. }
  163.  
  164. /*****************************************************************************
  165. * DESCRIPTION:                                                               *
  166. *   Merges the two provided polygons. Pl1 is assumed to fully contain Pl2.   *
  167. *   Pl1/2 are assumed to be convex. Pl2 vertex list is reversed and the two  *
  168. * polygon's vertex lists are connected via the maximum X vertices.         *
  169. *   This function is destructive and Pl1/2 are modifed in place.         *
  170. *                                                                            *
  171. * PARAMETERS:                                                                *
  172. *   Pl1, Pl2:    The two polygons to merge into one.                         *
  173. *   Pl2:                                                                     *
  174. *                                                                            *
  175. * RETURN VALUE:                                                              *
  176. *   IPPolygonStruct:  The merged polygon.                                    *
  177. *****************************************************************************/
  178. static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
  179.                      IPPolygonStruct *Pl2)
  180. {
  181.     RealType MaxX;
  182.     IPVertexStruct *V, *VMaxX1Copy, *VMaxX2Copy,
  183.     *VMaxX1 = NULL,
  184.     *VMaxX2 = NULL;
  185.  
  186.     IritPrsrReverseVrtxList(Pl2);
  187.  
  188.     /* FInd the vertices in both polygons with the maximum X value. */
  189.     V = Pl1 -> PVertex;
  190.     MaxX = -INFINITY;
  191.     do {
  192.     if (V -> Coord[0] > MaxX) {
  193.         VMaxX1 = V;
  194.         MaxX = V -> Coord[0];
  195.     }
  196.     V = V -> Pnext;
  197.     } while (V != NULL && V != Pl1 -> PVertex);
  198.  
  199.     V = Pl2 -> PVertex;
  200.     MaxX = -INFINITY;
  201.     do {
  202.     if (V -> Coord[0] > MaxX) {
  203.         VMaxX2 = V;
  204.         MaxX = V -> Coord[0];
  205.     }
  206.     V = V -> Pnext;
  207.     } while (V != NULL && V != Pl2 -> PVertex);
  208.  
  209.     /* Duplicate this maximum points. */
  210.     VMaxX1Copy = IPAllocVertex(VMaxX1 -> Tags, VMaxX1 -> Count, NULL,
  211.                    VMaxX1 -> Pnext);
  212.     PT_COPY(VMaxX1Copy -> Coord, VMaxX1 -> Coord);
  213.     PT_COPY(VMaxX1Copy -> Normal, VMaxX1 -> Normal);
  214.  
  215.     VMaxX2Copy = IPAllocVertex(VMaxX2 -> Tags, VMaxX2 -> Count, NULL,
  216.                    VMaxX2 -> Pnext);
  217.     PT_COPY(VMaxX2Copy -> Coord, VMaxX2 -> Coord);
  218.     PT_COPY(VMaxX2Copy -> Normal, VMaxX2 -> Normal);
  219.  
  220.     /* And exchange pointers. */
  221.     VMaxX1 -> Pnext = VMaxX2Copy;
  222.     IP_SET_INTERNAL_VRTX(VMaxX1);
  223.     VMaxX2 -> Pnext = VMaxX1Copy;
  224.     IP_SET_INTERNAL_VRTX(VMaxX2);
  225.  
  226.     Pl2 -> PVertex = NULL;
  227.     IPFreePolygonList(Pl2);
  228.  
  229.     IP_RST_CONVEX_POLY(Pl1);
  230.  
  231.     return Pl1;
  232. }
  233.  
  234. /*****************************************************************************
  235. * DESCRIPTION:                                                               *
  236. *   Connects the two provided lists of polylines into a closed polygon.         *
  237. * Pl1/2 are being used by this routine and being destroyed.             *
  238. *                                                                            *
  239. * PARAMETERS:                                                                *
  240. *   Pl1, Pl2:   The two lists of polylines to merge into one closed polygon. *
  241. *                                                                            *
  242. * RETURN VALUE:                                                              *
  243. *   IPPolygonStruct:  The constructed polygon.                               *
  244. *****************************************************************************/
  245. static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
  246.                      IPPolygonStruct *Pl2)
  247. {
  248.     IPVertexStruct *VTail;
  249.     IPPolygonStruct *Pl, *PlLast,
  250.     *PlOut = NULL;
  251.  
  252.     /* Chain the two lists into one: */
  253.     for (Pl = Pl1; Pl -> Pnext != NULL; Pl = Pl -> Pnext);
  254.     Pl -> Pnext = Pl2;
  255.     for (VTail = Pl1 -> PVertex; VTail -> Pnext != NULL; VTail = VTail -> Pnext);
  256.  
  257.     while (Pl1 != NULL)
  258.     {
  259.     for (PlLast = Pl1, Pl = Pl1 -> Pnext;
  260.          Pl != NULL &&
  261.          !BOOL_PT_APX_EQ(Pl -> PVertex -> Coord, VTail -> Coord);
  262.          PlLast = Pl, Pl = Pl -> Pnext);
  263.     if (Pl == NULL) {
  264.         IritFatalError("Boolean2D: Failed to match polylines.");
  265.         return NULL;
  266.     }
  267.  
  268.     VTail -> Pnext = Pl -> PVertex -> Pnext;
  269.  
  270.     /* Free the merged polyline (with its first vertex). */
  271.     PlLast -> Pnext = Pl -> Pnext;
  272.     Pl -> PVertex -> Pnext = NULL;
  273.     IPFreePolygon(Pl);
  274.  
  275.     /* Update the Tail pointer. */
  276.     for ( ; VTail -> Pnext != NULL; VTail = VTail -> Pnext);
  277.  
  278.     if (BOOL_PT_APX_EQ(VTail -> Coord, Pl1 -> PVertex -> Coord)) {
  279.         /* We closed a loop here. Add to output list. */
  280.         Pl = Pl1 -> Pnext;
  281.         Pl1 -> Pnext = PlOut;
  282.         PlOut = Pl1;
  283.  
  284.         /* Close the loop and remove the duplicate vertex. */
  285.         VTail -> Pnext = Pl1 -> PVertex -> Pnext;
  286.         IPFreeVertex(Pl1 -> PVertex);
  287.         Pl1 -> PVertex = VTail;
  288.  
  289.         /* Continue with next polygon. */
  290.         if ((Pl1 = Pl) != NULL) {
  291.         for (VTail = Pl1 -> PVertex;
  292.              VTail -> Pnext != NULL;
  293.              VTail = VTail -> Pnext);
  294.         }
  295.     }
  296.     }
  297.  
  298.     return PlOut;
  299. }
  300.  
  301. /*****************************************************************************
  302. * DESCRIPTION:                                                               *
  303. *   Given two polygons, Detect all edges in Pl1 that intersect with edges in *
  304. * Pl2. Returned is the information about all intersections as a Bool2DInter  *
  305. * structure list.                                 *
  306. *                                                                            *
  307. * PARAMETERS:                                                                *
  308. *   Poly1, Poly2: The two polygons to intersect.                             *
  309. *   Poly2:                                                                   *
  310. *                                                                            *
  311. * RETURN VALUE:                                                              *
  312. *   Bool2DInterStruct *:  Intersection information.                          *
  313. *****************************************************************************/
  314. static Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Poly1,
  315.                          IPPolygonStruct *Poly2)
  316. {
  317.     Bool2DInterStruct *Bool2D,
  318.     *Bool2DHead = NULL;
  319.     RealType Pl1Param, Pl2Param;
  320.     RealType *Pl1, *Pl2, t1, t2;
  321.     PointType Pt1, Pt2;
  322.     VectorType Vl1, Vl2;
  323.     IPVertexStruct *V1, *V2,
  324.     *V1Head = Poly1 -> PVertex,
  325.     *V2Head = Poly2 -> PVertex;
  326.  
  327.     V1 = V1Head;
  328.     Pl1Param = 0.0;
  329.     do {
  330.     Pl1 = V1 -> Coord;
  331.     PT_SUB(Vl1, V1 -> Pnext -> Coord, Pl1);
  332.  
  333.     V2 = V2Head;
  334.         Pl2Param = 0.0;
  335.     do {
  336.         Pl2 = V2 -> Coord;
  337.         PT_SUB(Vl2, V2 -> Pnext -> Coord, Pl2);
  338.  
  339.         if (CG2PointsFromLineLine(Pl1, Vl1, Pl2, Vl2, Pt1, &t1, Pt2, &t2) &&
  340.         t1 > 0.0 && t1 <= 1.0 && t2 > 0.0 && t2 <= 1.0) {
  341.         /* We detected an intersection here. */
  342.         Bool2D = (Bool2DInterStruct *)
  343.                    IritMalloc(sizeof(Bool2DInterStruct));
  344.         PT_COPY(Bool2D -> InterPt, Pt1);
  345.         InterpNrmlBetweenTwo2(Pt1, Bool2D -> Normal, V1, V2);
  346.  
  347.         Bool2D -> Poly1Vrtx = V1;
  348.         Bool2D -> Param1 = Pl1Param + t1;
  349.         Bool2D -> Poly2Vrtx = V2;
  350.         Bool2D -> Param2 = Pl2Param + t2;
  351.  
  352.         Bool2D -> Pnext = Bool2DHead;
  353.         Bool2DHead = Bool2D;
  354.         }
  355.  
  356.         Pl2Param += 1.0;
  357.         V2 = V2 -> Pnext;
  358.     }
  359.     while (V2 != NULL && V2 != V2Head);
  360.  
  361.     Pl1Param += 1.0;
  362.     V1 = V1 -> Pnext;
  363.     }
  364.     while (V1 != NULL && V1 != V1Head);
  365.  
  366.     if (Bool2DHead != NULL && Bool2DHead -> Pnext == NULL) {
  367.     /* If only one intersection - ignore it (point intersection). */
  368.     IritFree((VoidPtr) Bool2DHead);
  369.     Bool2DHead = NULL;
  370.     }
  371.     
  372.     return Bool2DHead;
  373. }
  374.  
  375. /*****************************************************************************
  376. * DESCRIPTION:                                                               *
  377. *   Sorts the provided list with according to Param1 (First == TRUE) or      *
  378. * Param2 (First == FALSE). Bool2D is sorted in place.                        *
  379. *                                                                            *
  380. * PARAMETERS:                                                                *
  381. *   Bool2D:      List of intersection locations to sort.                     *
  382. *   First:       TRUE if sort according to first, FALSE otherwise.           *
  383. *                                                                            *
  384. * RETURN VALUE:                                                              *
  385. *   void                                                                     *
  386. *****************************************************************************/
  387. static void SortParam(Bool2DInterStruct **Bool2D, int First)
  388. {
  389.     Bool2DInterStruct
  390.     *Bool2DSorted = NULL;
  391.  
  392.     while (*Bool2D != NULL) {
  393.     Bool2DInterStruct *BTmp,
  394.         *B = *Bool2D;
  395.  
  396.     *Bool2D = (*Bool2D) -> Pnext;
  397.     B -> Pnext = NULL;
  398.  
  399.     if (Bool2DSorted) {
  400.         if ((First && Bool2DSorted -> Param1 > B -> Param1) ||
  401.         (!First && Bool2DSorted -> Param2 > B -> Param2)) {
  402.         /* Put it as first in list. */
  403.         B -> Pnext = Bool2DSorted;
  404.         Bool2DSorted = B;
  405.         }
  406.         else {
  407.         for (BTmp = Bool2DSorted;
  408.              BTmp -> Pnext != NULL;
  409.              BTmp = BTmp -> Pnext)
  410.             if ((First && BTmp -> Pnext -> Param1 > B -> Param1) ||
  411.             (!First && BTmp -> Pnext -> Param2 > B -> Param2))
  412.             break;
  413.         B -> Pnext = BTmp -> Pnext;
  414.         BTmp -> Pnext = B;
  415.         }
  416.     }
  417.     else
  418.         Bool2DSorted = B;
  419.     }
  420.  
  421.     *Bool2D = Bool2DSorted;
  422. }
  423.  
  424. /*****************************************************************************
  425. * DESCRIPTION:                                                               *
  426. * Given two polygons, Computes the region(s) of Pl1 in or out of Pl2.        *
  427. *                                                                            *
  428. * PARAMETERS:                                                                *
  429. *   Pl1, Pl2:      Polygons to compute Pl1 in or out Pl2 for.                *
  430. *   Bool2D:        List of intersection locations.                           *
  431. *   Pl1First:      If in fact Pl1 is second in Bool2D.                       *
  432. *   ComputeOut:    TRUE for Pl1 Out Pl2, FALSE for Pl1 in Pl2.               *
  433. *                                                                            *
  434. * RETURN VALUE:                                                              *
  435. *   IPPolygonStruct:  Retulting Boolean.                                     *
  436. *****************************************************************************/
  437. static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
  438.                             IPPolygonStruct *Pl2,
  439.                             Bool2DInterStruct **Bool2D,
  440.                             int Pl1First,
  441.                         int ComputeOut)
  442. {
  443.     VectorType V1, V2;
  444.     IPVertexStruct *V, *VTail, *VTmp, *VTmp2,
  445.     *VHead = Pl1 -> PVertex;
  446.     IPPolygonStruct *Pl,
  447.     *PlOut = NULL;
  448.     Bool2DInterStruct *B, *NextB;
  449.  
  450.     SortParam(Bool2D, Pl1First);
  451.  
  452.     for (B = *Bool2D; B != NULL; B = B -> Pnext) {
  453.     NextB = B -> Pnext ? B -> Pnext : *Bool2D;
  454.  
  455.     VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
  456.     if (BOOL_PT_APX_EQ(B -> InterPt, VTmp -> Coord))
  457.         PT_SUB(V1, VTmp -> Pnext -> Coord, B -> InterPt)
  458.     else
  459.         PT_SUB(V1, B -> InterPt, VTmp -> Coord)
  460.  
  461.     VTmp = Pl1First ? B -> Poly2Vrtx : B -> Poly1Vrtx;
  462.     if (BOOL_PT_APX_EQ(B -> InterPt, VTmp -> Coord))
  463.         PT_SUB(V2, VTmp -> Pnext -> Coord, B -> InterPt)
  464.     else
  465.         PT_SUB(V2, B -> InterPt, VTmp -> Coord)
  466.  
  467.         if ((Z_CROSS_PROD(V1, V2) < 0.0) ^ (ComputeOut != FALSE)) {
  468.         VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
  469.         VHead = VTail = IPAllocVertex(VTmp -> Count, VTmp -> Tags,
  470.                       NULL, NULL);
  471.         PT_COPY(VHead -> Coord, B -> InterPt);
  472.         PT_COPY(VHead -> Normal, B -> Normal);
  473.  
  474.         VTmp2 = Pl1First ? NextB -> Poly1Vrtx : NextB -> Poly2Vrtx;
  475.         if (VTmp != VTmp2)
  476.         for (V = VTmp -> Pnext;
  477.              V != VTmp2 -> Pnext;
  478.              V = V -> Pnext) {
  479.             VTail -> Pnext =
  480.             IPAllocVertex(V -> Count, V -> Tags, NULL, NULL);
  481.             VTail = VTail -> Pnext;
  482.             PT_COPY(VTail -> Coord, V -> Coord);
  483.         PT_COPY(VTail -> Normal, V -> Normal);
  484.         }
  485.  
  486.         VTail -> Pnext = IPAllocVertex(VTmp2 -> Count, VTmp2 -> Tags,
  487.                        NULL, NULL);
  488.         VTail = VTail -> Pnext;
  489.         PT_COPY(VTail -> Coord, NextB -> InterPt);
  490.         PT_COPY(VTail -> Normal, NextB -> Normal);
  491.  
  492.         Pl = IPAllocPolygon(0, 0, VHead, NULL);
  493.         PLANE_COPY(Pl -> Plane, Pl1 -> Plane);
  494.         Pl -> Pnext = PlOut;
  495.         PlOut = Pl;
  496.     }
  497.     }
  498.  
  499.     if (PlOut == NULL)
  500.     IritFatalError("Bool2D: Failed to compute in/out.");
  501.     return PlOut;
  502. }
  503.  
  504. /*****************************************************************************
  505. * DESCRIPTION:                                                               *
  506. *   Given a polyline (= list of IPVertexStruct), computes the reverse of     *
  507. * the list, in place. Returns pointer to reversed list.                 *
  508. *                                                                            *
  509. * PARAMETERS:                                                                *
  510. *   PlHead:        Polyline to reverse.                                      *
  511. *                                                                            *
  512. * RETURN VALUE:                                                              *
  513. *   IPPolygonStruct:    Reversed polyline.                                   *
  514. *****************************************************************************/
  515. static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead)
  516. {
  517.     IPPolygonStruct *Pl;
  518.  
  519.     for (Pl = PlHead; Pl != NULL; Pl = Pl -> Pnext) {
  520.     IPVertexStruct *VNextNext, *V, *VNext;
  521.  
  522.     V = Pl -> PVertex;
  523.     VNext = V -> Pnext;
  524.  
  525.     while (VNext != NULL) {
  526.         VNextNext = VNext -> Pnext;
  527.         VNext -> Pnext = V;                 /* Reverse the pointer! */
  528.  
  529.         V = VNext;               /* Advance all 3 pointers by one. */
  530.         VNext = VNextNext;
  531.     }
  532.     Pl -> PVertex -> Pnext = NULL;
  533.     Pl -> PVertex = V;
  534.  
  535.     /* Move the Tags. */
  536.     while (V -> Pnext != NULL) {
  537.         V -> Tags = V -> Pnext -> Tags;
  538.         V -> Count = V -> Pnext -> Count;
  539.  
  540.         V = V -> Pnext;
  541.     }
  542.     }
  543.     return PlHead;
  544. }
  545.  
  546. #ifdef DEBUG2
  547.  
  548. /*****************************************************************************
  549. * DESCRIPTION:                                                               *
  550. *   Print the content of the given vertex list, to standard output.         *
  551. *                                                                            *
  552. * PARAMETERS:                                                                *
  553. *   V:        Vertex list to print.                                          *
  554. *                                                                            *
  555. * RETURN VALUE:                                                              *
  556. *   void                                                                     *
  557. *****************************************************************************/
  558. static void PrintVrtxList(IPVertexStruct *V)
  559. {
  560.     IPVertexStruct
  561.     *VHead = V;
  562.  
  563.     do {
  564.     printf("    %12lf %12lf %12lf",
  565.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  566.     if (IS_INTERNAL_EDGE(V))
  567.         printf(" (Internal)\n");
  568.     else
  569.         printf("\n");
  570.     V = V -> Pnext;
  571.     }
  572.     while (V!= NULL && V != VHead);
  573. }
  574.  
  575. #endif /* DEBUG2 */
  576.